package com.xyj.week01;

/**
 * 题目：判断链表有没有环
 */
public class T1 {


    public static void main(String[] args) {
        //初始化环形链表
        Node node = new Node(0);
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        node.next=node1;
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node2;
        ifHasCircle(node);
        //判断是否有环
        ifHasCircle2(node);
    }

    /**
     * 解法1：如果没有环的话，就会返回，
     * 可是如果有环的话，就会陷入死循环
     * @param head 链表头节点
     * @return 是否有环
     */
    public static Boolean ifHasCircle(Node head){
        while (head!=null){
            head=head.next;
        }
        System.out.println("No circle");
        return false;
    }


    /**
     * 解法2：定义两个指针，一个快指针和一个慢指针，
     * 快指针一次走两步，慢指针一次走一步，当慢指针和快指针相遇  说明有环存在
     *
     */
    public static Node ifHasCircle2(Node head){
        //慢指针
        Node slow=head;
        //快指针
        Node fast=head;

        while (fast.next!=null&&fast.next.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            if (fast==slow){
                System.out.println("have a circle, the meet point "+slow);
                return slow;
            }
        }
        return null;
    }

}
